\chapter{Source Coding Tools}

      Here is a description of the various source coding tools
      provided by the library.


\section{Random numbers and source generation}

    The library provides various source generation
    functions. Memoryless sources include discrete sources such as a
    binary source, and a generic discrete source generator from the
    discrete PDF (probability density function). Memoryless
    continous sources include a uniform source, a gaussian source and
    a generic continuous source generator from the continuous
    PDF. No correlated source generators are provided yet.


\subsection{Random number generator}

    The pseudo-random number generator provided by libit is based on
  the MT19937 algorithm. It has a large period of $10^{623}$ which is much
  better than the standard C function \function{rand()}. It should
  \emph{not} be used for cryptography without proper
  secure hashing of the generated words. For more information on this
  generator, see M. Matsumoto and T. Nishimura, "Mersenne Twister: A
  623-Dimensionally Equidistributed Uniform Pseudo-Random Number
  Generator", ACM Transactions on Modeling and Computer Simulation,
  Vol. 8, No. 1, January 1998, pp 3--30.  

    A random number uniformly distributed in [0,1) is generated using the function
    \function{it\_rand()}, which returns a double. Note that the
    resolution of this number is actually 32-bit (therefore the term
    'uniform' is not strictly correct). The random number generator
    need not be seeded if you want to produce the same sequence of
    pseudo-random numbers at each execution. Otherwise, the function
    \function{it\_seed()} is provided which initializes the random
    number generator with a given 32-bit seed. The generator can also
    be initialized from the system clock using
    \function{it\_randomize()}. Keep in mind that all these
    initialization procedures are \emph{not secure} enough for any
    cryptographic use.


\begin{program}{Random number generation example}{pro:randnumbgen}
/* initialize the pseudo-random generator from the system clock */
it_randomize();

/* generate a random number uniformly distributed in [0,1) */
double s = it_rand();
\end{program}

    Non-uniform random number generation is provided in the form of a
    normal (Gaussian) generator and a generic generator from the
    probability distribution function. The normal generator returns a
    sample of a normally distributed source, that is a Gaussian source
    of zero mean and variance one. The method used for generating such
    a sample is the Box-Mueller method.

\begin{program}{Normally distributed random number generation example}{pro:normalrandgen}
/* initialize the pseudo-random generator from an integer */
it_seed(0xdeadbeef);

/* generate a normally distributed random number */
double s = it_randn();
\end{program}

    The generic random number generator \function{it\_randpdf()} returns a sample of a
    source distributed according to the specified PDF. This PDF is
    defined using an it\_function, assuming it is null outside a
    specified range and that it's maximum value is taken in zero. For
    more information on functions, see Section~\ref{sec:functions}. The
    method used to generate a sample is the acceptance-rejection
    method.

\begin{program}{Generic random number generation example}{pro:genrandnumb}
/*-- probability density function declaration --*/

/* parameters of the Laplacian distribution */
it_function_args(laplacian_pdf) {
  double lambda;
};
/* Laplacian probability density function definition (symmetric) */
it_function(laplacian_pdf)
{
  double lambda = it_this->lambda;

  return(1. / (2.*lambda) * exp(-fabs(x) / lambda));
}

/*-- generate a random number according to this PDF --*/

/* declare the Laplacian parameters */
it_function_args(laplacian_pdf) laplacian_args;

/* set the Laplacian parameter lambda to 1/sqrt(2) (variance equal to 1) */
laplacian_args.lambda = 1/sqrt(2.0);

/* generate laplacian source of 20 samples, assuming the distribution is */
/* null outside the range [-10,10]                                       */
double s = it_randpdf(-10, 10, laplacian_pdf, &laplacian_args);
\end{program}


\subsection{Discrete sources}
\label{sec:discretesources}

    To generate a binary random vector, the function 
    \function{source\_binary()} is provided. It
    creates a random bvec of zeroes and ones according to the
    probability of the zero bit. The generic memoryless discrete
    source generator takes a vector representing the probability of
    each symbol. The length of the vector corresponds to the number of
    discrete symbols, where each element represents the probability of
    drawing the corresponding symbol. Therefore, this PDF vector must
    sum to one. The random vector is generated by drawing a uniform
    random number and taking the inverse of the cumulative density
    function.

    The following example shows how to generate such random vectors.

\begin{program}{Discrete random source generation example}{pro:discretesource}
/* generate a binary source of 20 samples with more zeroes than ones */
bvec B = source_binary(20, 0.7);

/* generate a 4-ary discrete source of 20 samples according to the PDF */
vec pdf = vec_new_string("0.5 0.3 0.1 0.1"); /* probability density function */
S = source_memoryless(20, pdf );
\end{program}


\subsection{Continuous sources}

A vector of uniformly distributed samples taken in the range [a,b) is
generated using the function \function{source\_uniform()} and specifying
the bounds \emph{a} and
\emph{b}. Similarly, a vector of normally (Gaussian)
distributed samples is generated using 
\function{source\_gaussian()} and specifying
the mean and variance of the distribution. The following example shows
how to generate these random vectors.

\begin{program}{Uniform and Gaussian random source generation example}{pro:unifgaussrandsourcegen}
/* generate a uniform source of 20 samples distributed in [0,1] */
vec v = source_binary(20, 0, 1);

/* generate a gaussian source of 20 samples with mean 0 and variance 1 */
vec g = source_gaussian(20, 0, 1);
\end{program}

    Other memoryless random sources can be generated by providing the
    PDF as an it\_function and calling 
    \function{source\_pdf()}. For more information
    on functions, see Section~\ref{sec:functions}. The pdf must be
    centered on its maximum value and bounds must be provided where
    the PDF may be assumed to be zero. The following example shows how
    to draw a random memoryless vector from a Laplacian distribution,
    using the function definition from Example~\ref{pro:genrandsource}.

\begin{program}{Generic random source generation example}{pro:genrandsource}
/* declare the Laplacian parameters */
it_function_args(laplacian_pdf) laplacian_args;

/* set the Laplacian parameter lambda to 1/sqrt(2) (variance equal to 1) */
laplacian_args.lambda = 1/sqrt(2.0);

/* generate laplacian source of 20 samples, assuming the distribution is */
/* null outside the range [-10,10]                                       */
source = source_pdf(20, -10, 10, laplacian_pdf, &laplacian_args);
\end{program}


\section{Quantization}

      Various quantizers are provided in an object oriented
      hierarchy. All derive from the it\_quantizer\_t object, which is
      the vector quantizer. Currently, the quantizers described in 
Table~\ref{tab:quantizertypes} are defined. 

\begin{table}
\begin{center}
\begin{tabular}{|p{5cm}p{5cm}|}
\hline
       Object & Quantizer \\
\hline
          it\_quantizer\_t & 
          Vector quantizer \\
          it\_scalar\_quantizer\_t & 
          Scalar quantizer \\
          it\_uniform\_quantizer\_t & 
          Uniform scalar quantizer \\
          it\_trellis\_coded\_quantizer\_t & 
          Trellis coded quantizer \\
\hline
\end{tabular}
\label{tab:quantizertypes}
\caption{Quantizers}
\end{center}
\end{table}


      A value is quantized to an index with the
      \function{it\_quantize()} call. A value is dequantized using the
      \function{it\_dequantize()} call. A whole
      real-valued vec can be quantized to an ivec using the
      \function{it\_quantize\_vec()} call, and
      dequantized with the 
      \function{it\_dequantize\_vec()}
      call. Similarly matrices can be quantized and dequantized row by
      row with the 
      \function{it\_quantize\_mat()} and
      \function{it\_dequantize\_mat()} calls.

      The default scalar quantizer can be initilized from a
      codebook. Quantization is done using a logarithmic search inside
      that codebook for the closest codeword. Dequantization done in a
      much faster way by simply indexing the codebook. The 
      \function{lloyd\_max()} call can be used to
      compute the optimal codebook of source (minimizing the
      quantization distortion for a given fixed rate). Here is an
      example on how to build the Lloyd-Max quantizer with 4 levels
      for the gaussian source of zero mean and variance 1. We use the
      gaussian function defined in Section~\ref{sec:functions}. For
      more information on functions, refer to that section.

  \begin{program}{LLoyd-Max quantization example}{pro:lloydmax}
  /* set the standard deviation of the gaussian to 1 */
  gaussian_args.sigma = 1.0; 
  /* generate the Lloyd-Max quantization codebook for 4 levels */
  /* The pdf is limited to the range [-5,5] (assumed equal to 0 outside) */
  codebook = lloyd_max(gaussian, &gaussian_args, -5, 5, 4);

  /* create the associated quantizer */
  it_scalar_quantizer_t quantizer = it_scalar_quantizer_new(codebook);

  /* generate a random vector distributed normally */
  source = source_gaussian(100000, 0, gaussian_args.sigma);

  /* quantize */
  ivec qsource = it_quantize_vec(quantizer, source);

  /* dequantize */
  vec rec = it_dequantize_vec(quantizer, qsource);
\end{program}

      The uniform scalar quantizer can be initialized either from the
      position of the center and the step, or from the expected range
      of the values and the number of quantization levels. The first
      version uses the 
      \function{it\_uniform\_quantizer\_new\_from\_center()}
      call and can be given a factor to have a larger central zone
      (dead-zone). 

	The second versions is created using the
      \function{it\_uniform\_quantizer\_new\_from\_range()}
      call. The uniform scalar quantizer uses a division for
      quantization which is much faster than the generic logarithm
      search algorithm. Here is an example on how to use each version:

  \begin{program}{Uniform scalar quantization example}{pro:uniformquantizer}
  /* create a random vector uniformly distributed in [0,1] */
  vec source = source_uniform_01(100000);

  /* create a new uniform quantizer with 256 levels
     equally spread in the [0,1] range              */
  it_uniform_quantizer_t uniq =
      it_uniform_quantizer_new_from_range(256, 0.0, 1.0);

  /* quantize / dequantize */
  ivec qsource = it_quantize_vec(uniq, source);
  vec rec = it_dequantize_vec(uniq, qsource);

  /* create a new uniform quantizer with step 1/256 centered on 0
     with a dead-zone of twice the step size                      */
  it_uniform_quantizer_t uniq =
      it_uniform_quantizer_new_from_center(0, 1/256., 2.0);

  /* quantize / dequantize */
  ivec qsource = it_quantize_vec(uniq, source);
  vec rec = it_dequantize_vec(uniq, qsource);
\end{program}

      The trellis-coded quantizer (TCQ) is built from any scalar
      quantizer (uniform or generic) and a convolutional code. TCQ is
      a fast vector quantization technique achieving near optimal
      performance. It is based on the set partitioning by a
      convolutional code of the product codebook of a scalar
      quantizer. For more information on TCQ, refer to "M.W. Marcellin
      and T.R. Fisher, Trellis-coded quantization of memoryless and
      gauss-markov sources, IEEE Trans. Comm., 38:82--93,
      Jan. 1990". Here is an example on how to define and use such a
      quantizer:

 \begin{program}{TCQ example}{pro:tcq}
  /* generator polynomials for the convolutional code (rate 1/2) */
  imat generator = imat_new(1, 2); 
  generator[0][0] = 0133;
  generator[0][1] = 0171;
  /* create a convolutional code */
  it_convolutional_code_t *code = it_convolutional_code_new(generator);

  /* create a uniform quantizer with 512 levels */
  uniq = it_uniform_quantizer_new_from_range(512, 0.0, 1.0);
  /* create a TCQ quantizer from the uniform quantizer and the convolutional code */
  tcq = it_trellis_coded_quantizer_new_partition(code, uniq);

  /* create a random vector uniformly distributed in [0,1] */
  vec source = source_uniform_01(100000);

  /* quantize / dequantize */
  ivec qsource = it_quantize_vec(tcq, source);
  vec rec = it_dequantize_vec(tcq, qsource);
\end{program}

\section{Variable Length Codes}

In the following, the term Variable Length Code (VLC)
stands for a scalar variable length code over a finite alphabet. 
Although strictly speaking, arithmetic codes are 
variable length codes, arithmetic codes are not covered by this term. 
A variable length code is defined as a set of binary codewords.  
Such a code is a prefix code, i.e. a given codeword can not be 
the prefix of another.  

In the library, the typename for Variable Length Codes objects is vlc\_t. 
The users should only manipulate pointers vlc\_t *. 
The set of supported construction methods for Variable Length Codes is
given below. All these methods return an allocated vlc\_t pointer 
that allows to handle the corresponding object. 


\begin{table}
\begin{center}
\begin{tabular}{|p{3.5cm}p{3cm}p{8.5cm}|}
\hline
       Method & 
       Function name & 
       Description \\
\hline 

          Fixed length Code & 
          vlc\_flc & 
          All the codewords of the same size (lexicographic) \\
          Huffman & 
          vlc\_huffman & 
          The optimal Variable Length Code \\
          Hu-Tucker & 
          vlc\_hu\_tucker & 
          The optimal lexicographic Variable Length Code \\
          Generic & 
          vlc\_read & 
          Custom code entered by the user as a string \\
\hline
\end{tabular}
\label{tab:vlcconstruction}
\caption{Variable Length Codes construction methods}
\end{center}
\end{table}


The variable length encoder takes an input vector of symbols and
outputs a vector of bits. The symbols are represented by integers
between $0$ and $N-1$, where $N$ is the number of symbols handled by the
variable length code. The function
\function{vlc\_encode\_concat()} is used for the encoding. It,
takes the input vector of integers (type ivec) and produces a
bitstream represented by a byte vector (bvec). The decoder takes such
a bitstream as an input and allows to recover the original vector. It
is handled with function vlc\_decode\_concat.

Here is an example on how to define and use a variable length code:

\begin{program}{VLC example}{pro:vlc}
  /* The probability distribution function of the source        */
  vec pdf = vec_new_string( "0.5 0.3 0.1 0.1" );

  /* Create an Huffman code optimum for the source pdf          */
  vlc_t * vlc = vlc_huffman( pdf );

  /* Generate a sequence according to the given probability law */
  int N = 20;
  ivec S = source_memoryless( N, pdf );

  /* Encode and decode the sequence S with the Huffman Code     */
  bvec B = vlc_encode_concat( vlc, S );
  ivec D = vlc_decode_concat( vlc, B );

  /* Print the vectors S, B and D                               */
  it_printf( "S = $d\nB = $b\nD = $d\n", S, B, D );

  /* Print the mean description length of the code and the 
     observed average description length                        */
  printf( "Mdl             = %lf\n", vlc_mdl( vlc, pdf ) );
  printf( "Obs. av. length = %lf\n",
            bvec_length( B ) / (double) ivec_length( S ) );

  /* Delete the code and defines an user defined code such that 
     its Kraft sum not equal to 1 . Print the code.             */
  vlc_delete( vlc );
  vlc = vlc_read( "{0 11 101 1001}" );
  printf( "Kraft sum       = %lf\n", vlc_kraft_sum( vlc ) );
  printf( "Custom Code     = " );
  vlc_print( vlc );
  printf( "\n" );
  
  vlc_delete( vlc );
  ivec_delete( S );
  ivec_delete( D );
  bvec_delete( B );

  /*------------------------------------------------------------
     The program generate something like that:

  S = [0 2 0 1 0 1 2 3 1 0 0 0 0 0 2 0 0 1 3 2]
  B = [0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0 0]
  D = [0 2 0 1 0 1 2 3 1 0 0 0 0 0 2 0 0 1 3 2]
  Mdl             = 1.700000
  Obs. av. length = 1.800000
  Kraft sum       = 0.937500
  Custom Code     = {0 11 101 1001}                             */
\end{program}


Note that the users should not handle directly vlc\_t objects but
rather the corresponding pointers. The memory allocated by these
functions should be freed with the function 
\function{vlc\_delete()}.


